#define _CRT_SECURE_NO_WARNINGS 1
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
int n, m;
class Solution {
public:

    int dfs(int x, int y, vector<vector<int>>& f, vector<vector<int> >& matrix) {
        if (f[x][y]) {
            return f[x][y];
        }
        f[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x;
            int b = dy[i] + y;
            if (a >= 0 && a < n && b >= 0 && b<m && matrix[a][b]>matrix[x][y]) {
                f[x][y] = max(f[x][y], dfs(a, b, f, matrix) + 1);
            }
        }
        return f[x][y];
    }
    int solve(vector<vector<int> >& matrix) {
        n = matrix.size();
        m = matrix[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = max(ans, dfs(i, j, f, matrix));
            }
        }
        return ans;
    }
};


int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
int n, m;
typedef pair<int, int> PII;
class Solution {
public:

    int top(vector<vector<int>>& d, vector<vector<int> >& matrix) {
        queue<PII> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (d[i][j] == 0) {
                    q.push({ i,j });
                }
            }
        }

        int st = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto it = q.front();
                q.pop();

                int a = it.first;
                int b = it.second;
                for (int i = 0; i < 4; i++) {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < n && y >= 0 && y < m && matrix[a][b] < matrix[x][y]) {
                        d[x][y]--;
                        if (d[x][y] == 0) {
                            q.push({ x,y });
                        }
                    }
                }
            }
            st++;
        }
        return st;

    }
    int solve(vector<vector<int> >& matrix) {
        n = matrix.size();
        m = matrix[0].size();
        vector<vector<int>> d(n + 1, vector<int>(m + 1));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < 4; k++) {
                    int a = i + dx[k];
                    int b = j + dy[k];
                    if (a >= 0 && a < n && b >= 0 && b<m && matrix[a][b]>matrix[i][j]) {
                        d[a][b]++;
                    }
                }
            }
        }
        return top(d, matrix);
    }
};